// 给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
// 换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
// 以数组形式返回答案。



// 破解方法
const smallerNumbersThanCurrent1 = function (nums: number[]): number[] {
    const res: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        let count: number = 0;
        for (let j = 0; j < nums.length; j++) {
            if (nums[j] < nums[i]) {
                count++;
            }
        }
        res.push(count);
    }
    return res;
};


// 计数排序方法
const smallerNumbersThanCurrent2 = function (nums: number[]): number[] {
    const countMap: number[] = new Array(101).fill(0); // 频次数组
    const res: number[] = []; // 结果数组
    for (let num of nums) { // 统计数组元素出现个数
        countMap[num]++;
    }
    // 计算结果数组，加和小于当前元素的所有频次
    for (let i = 0; i < nums.length; i++) {
        let currSum: number = 0;
        for (let j = 0; j < nums[i]; j++) {
            currSum += countMap[j];
        }
        res.push(currSum)
    }
    return res;
};


// 这道题是一道比较基础的题目
// 首先比较容易想到的是使用破解法
// 两层for循环进行求解，时间复杂度是On2
// 之后我们可以尝试使用计数排序的思路进行优化
// 首先可以考虑建立一个频次数组，
// countMap[i] 表示数字 i 出现的次数。
// 那么对于数字 i 而言，小于它的数目就为 countMap（0-i-1）的总和
// 这在一定程度上可以免去比较，是一种用空间换时间的经典思路
// 但要注意数组范围的值域，当数组范围的值域区间过大时可能会导致频次数组需要的空间变得极大
// 这在一定程度上会让这种计数排序方法的性能大打折扣。